#include<string.h>

void mergesort(int* arr,int* tmp,int left,int right)
{
    if(left>=right) return;
    int mid=left+(right-left)/2;
    mergesort(arr,tmp,left,mid);
    mergesort(arr,tmp,mid+1,right);
    int begin1=left,end1=mid,begin2=mid+1,end2=right,i=left;
    while(begin1<=end1&&begin2<=end2)
    {
        if(arr[begin1]<arr[begin2]) tmp[i++]=arr[begin1++];
        else tmp[i++]=arr[begin2++];
    }
    while(begin1<=end1) tmp[i++]=arr[begin1++];
    while(begin2<=end2) tmp[i++]=arr[begin2++];
    memcpy(arr+left,tmp+left,sizeof(int)*(end2-left+1));
}
